package algorithm.dongtaiguihua;


import org.junit.Test;

public class HuiwenStr {

  static String src = "\"cbbd\"";

  public static void main(String[] args) {

  }

  /**
   * 动态规划 时间复杂度 n^2,空间复杂度 n^2
   */
  @Test
  public void test() {

    src = "bb";
    //d[i][j] =   (si == sj) && ( j-i+1<4 || d[i+1][j-1] )

    int length = src.length();

    if (length < 2) {
      return;
    }
    boolean[][] d = new boolean[length ][length ];
    for (int i = 0; i < length ; i++) {
      d[i][i] = true;
    }

    // i为右边界限
    for (int i = 0; i < length ; i++) {
      // j为左边界
      for (int j = 0; j <= i; j++) {
        if (src.charAt(j) == src.charAt(i)) {
          if (i - j + 1 < 4) {
            d[j][i] = true;
          } else {
            d[j][i] = d[j + 1][i - 1];
          }
        }

        if (d[j][i]) {
          System.out.println(j + " " + src.substring(j, i + 1));
        }

      }

    }


  }

  /**
   * 中心扩展法 时间复杂度 n^2 ，空间复杂度 1
   */
  @Test
  public void test2() {
    int maxLeng = 0;
    int length = src.length();
    //length - 1 最右边的元素可以忽略了
    for (int i = 0; i < length - 1; i++) {
      //奇数 长度肯定是奇数
      int js = maxLen(src, i, i);
      //偶数 长度是偶数
      int os = maxLen(src, i, i + 1);
      //不论中心是奇数还是偶数，取长度最长
      int max = Math.max(js, os);

      // 长度1,3,5  这种奇数  或者 2 4 6 这种偶数，都可以用下面的r 和l表示出来
      // 。。。
      int r = 0;
      if (js > os) {
        r = i - max / 2;
      } else {
        r = i - (max / 2 - 1);
      }
      int l = r + max;
      if (max > maxLeng) {
        maxLeng = max;
        System.out.println("max:" + src.substring(r, l));
      }
      System.out.println(src.substring(r, l));

    }
  }

  public int maxLen(String src, int l, int r) {
    //循环扩散
    while (
            (l >= 0 && r < src.length()) &&
                    src.charAt(l) == src.charAt(r)
    ) {
      l--;
      r++;
    }

    return r - l - 1;
  }

  /**
   * 暴力解法 时间复杂度 n^3 ，空间复杂度 n
   */
  public void test3() {

  }


}
